/*************************************************************************
 * File Name:    Decode_Ways.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: Sat 02 Nov 2013 06:49:07 PM CST
 * 
 * Description:  
 |-----------------------------------------------------------------------
 | Problem: Decode Ways Total
 | A message containing letters from A-Z is being encoded to numbers using
 | the following mapping:
 |
 | 'A' -> 1
 | 'B' -> 2
 | ...
 | 'Z' -> 26
 |
 | Given an encoded message containing digits, determine the total number
 | of ways to decode it.
 |
 | For example,
 | Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
 |
 | The number of ways decoding "12" is 2.
 |------------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <iomanip>

using namespace std;

class Solution {
public:
    int numDecodings(string s) {
        if (s.size() == 0) return 0;
        
        int N = s.size();
        vector<int> dp(N + 1, 0);
        
        if (s[0] == '0') dp[0] = dp[1] = 0;
        else dp[0] = dp[1] = 1;
        
        for (int i = 2; i <= N; ++i) {
            if (s[i - 1] != '0') dp[i] = dp[i - 1];
            else dp[i] = 0;
            
            int t = 10 * (s[i - 2] - '0') + s[i - 1] - '0';
            if (t <= 26 && t >= 10) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[N];
    }
};

